#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

template<class T>
struct AVLTNode
{
	AVLTNode(const T& val = T())
		:_val = val
		,_left = nullptr
		,_right = nullptr
	{}
	AVLTNode<T>* _left;
	AVLTNode<T>* _right;
	T _val;
};

template<class T>
class AVLTree
{
	typedef AVLTNode<T> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}

	~AVLTree()
	{
		AVLDestory(_root);
	}

	bool Insert(const T& val)
	{
		return _Insert(_root, val);
	}

	void Inprint()
	{
		_Inprint(_root);
	}
private:
	AVLDestory(Node* root)
	{
		if (root == nullptr)
			return;

		AVLDestory(root->_left);
		AVLDestory(root->_right);
		delete root;
	}

	bool _Insert(Node* root, const T& val)
	{
		if (root == nullptr)
		{
			root = new Node(val);
			return true;
		}

		if (root->_val == val)
			return false;
		else if (root->_val < val)
			_Insert(root->_right, val);
		else
			_Insert(root->_left, val);
	}

	void _Inprint(Node* root)
	{
		if (root == nullptr)
			return;

		_Inprint(root->_left);
		cout << root->_val << endl;
		_Inprint(root->_right);
	}

	Node* _root;
};

int main()
{
	AVLTree<int> root;
	int a[] = { 3,6,1,5,8,7,0,9,2,4 };
	for (auto& i : a)
	{
		root.Insert(i);
	}

	root.Inprint();
	return 0;
}